package org.zn.note.jdk.container;

import java.io.*;
import java.util.*;
import java.util.concurrent.CopyOnWriteArrayList;

/**
 * {@link ArrayList} 非线程安全
 * 其实就是一个数组，可以随机访问随机添加删除等，然后来回挪动剩余元素，空间不够就扩容(new新的)
 * <p>
 * 1、为什么elementData是transient  --> {@link #testSerializeArrayList}
 * transient是不序列化该变量。通过readObject和writeObject序列化。可以避免elementData中null的部分。为了省空间。
 * <p>
 * 2、关于扩容
 * ① 每次扩当前容量的一半，int newCapacity = oldCapacity + (oldCapacity >> 1)  （x>>1 = x/2）
 * ② 最多容量 elementData[Integer.MAX_VALUE]
 * ③ 扩容少于10的，则直接扩到10，elementData[10]
 * ④ size是实际数据大小，不是数组大小，数组实际大小是elementData.length，一般 elementData.length > size
 * <p>
 * 3、关于modCount、ConcurrentModificationException (concurrent 同时、modification 修改)
 * 用Iterator、ForEach遍历时，如果修改ArrayList，则抛异常 {@link ConcurrentModificationException}
 * (用Iterator本身的remove是可以的，会修正expectedModCount；foreach不行）
 * 是为了快速失败，防止有
 * ① 在刚获取到Iterator或者刚开始ForEach时，expectedModCount = 当前modCount
 * ② 所有的修改ArrayList的行为，modCount++
 * ③ 遍历中每次循环都会校验 modCount != expectedModCount ==> ConcurrentModificationException
 * （当然，你自己写for来遍历，因为没检查modCount，所以肯定不会有这个问题）
 * 除了判断modCount，当 i > elementData.length时，也会ConcurrentModificationException
 * （在当前逻辑中就判断了，防止再到数组那层抛出数组越界）
 * 注意：
 * ① 这里并不是完全为了体现线程不安全，因为单线程也能抛这个异常。
 * ② 这是为了“尽力”保证在有人“读”的时候不能“改”！因为读写都在同一个地方，这也就有了后面的 {@link CopyOnWriteArrayList}
 * <p>
 * 4、为什么线程不安全
 * 其实就是ArrayList里面很多操作，本来应该是原子操作的，但是由多个步骤组成，这些步骤间又是可以被中断的。
 * 比如 elementData[size++] = a，这时有其他线程修改size，这个a就不一定赋值到哪里了。
 */
public class JdkArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {

    // capacity 容量
    private static final int DEFAULT_CAPACITY = 10;
    private static final Object[] EMPTY_ELEMENTDATA = {};
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    // transient 短暂的，序列化时，不序列化该变量
    // Array是Serializable，为啥还能序列化这个啊？因为有readObject和writeObject
    // elementData扩容后，里面是装不满的，只需要序列化有元素的，所以不序列化整个elementData，节省空间
    transient Object[] elementData;
    private int size;

    // 构造方法1：空
    public JdkArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }

    // 构造方法2：给初始大小
    public JdkArrayList(int initialCapacity) {
    }

    // 构造方法3：给初始内容
    public JdkArrayList(Collection<? extends E> c) {
    }

    @Override
    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean contains(Object o) {
        return indexOf(o) >= 0;
    }

    public int indexOf(Object o) { // 遍历找出第一个匹配的，O(n)
        if (o == null)
            for (int i = 0; i < size; i++) {
                if (elementData[i] == null) return i;
            }
        else
            for (int i = 0; i < size; i++) {
                if (o.equals(elementData[i])) return i;
            }
        return -1;
    }

    public int lastIndexOf(Object o) {
        return -1;
    } // 倒着遍历 for (int i = size-1; i >= 0; i--)

    public Object clone() {
        return null;
    } // 浅克隆:ArrayList本身是个新对象，但是里面内容都有原来的引用。 参见下面 testArrayListClone

    public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    } // 转成数组

    public <T> T[] toArray(T[] a) {
        return null;
    } // 带类型的

    E elementData(int index) {
        return (E) elementData[index];
    } // 随机访问

    @Override
    public E get(int index) {
        rangeCheck(index);
        return elementData(index);
    } // 检查边界，随机访问

    public E set(int index, E element) { // 检查边界，set值，返回旧值
        rangeCheck(index);
        E oldValue = elementData(index);
        elementData[index] = element;
        return oldValue;
    }

    public boolean add(E e) { // 不够用时再扩容
        ensureCapacityInternal(size + 1);
        elementData[size++] = e;
        return true;
    }

    public boolean addAll(Collection<? extends E> c) {
        return true;
    } // 加到当前数组后面，如果当前数据不够就扩容

    public boolean addAll(int index, Collection<? extends E> c) {
        return true;
    } // 插到当前数据中间

    public void add(int index, E element) { // 中间插入元素，每次都要把后面的元素往后挪
        rangeCheckForAdd(index);
        ensureCapacityInternal(size + 1); // 不够用时再扩容
        System.arraycopy(elementData, index, elementData, index + 1, size - index); // 往后挪
        elementData[index] = element;
        size++;
    }

    // 注意：remove和clear后，elementData[length]不变，仅仅是修改变量size
    public E remove(int index) {
        return null;
    } // add类似，不过是后面的往前挪

    public boolean remove(Object o) {
        return true;
    } // 先遍历找到第一个匹配的，然后后面的往前挪

    public void clear() {
    } // 遍历元素，全部=null，size=0

    public boolean removeAll(Collection<?> c) {
        return true;
    } // 移除c中包含的

    public boolean retainAll(Collection<?> c) {
        return true;
    } // 保留c中包含的

    public List<E> subList(int fromIndex, int toIndex) {
        return null;
    }

    // 扩容后装不满，可以trim。（trim 缩减）
    // size是实际内容多少，一般 size < elementData.length
    public void trimToSize() {
        modCount++;
        if (size < elementData.length)
            elementData = (size == 0) ? EMPTY_ELEMENTDATA : Arrays.copyOf(elementData, size);
    }

    // ensure 确保
    public void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) ? 0 : DEFAULT_CAPACITY;
        if (minCapacity > minExpand)
            ensureExplicitCapacity(minCapacity);
    }

    // calculate 计算
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        return minCapacity;
    }

    // Internal 内部
    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

    // Explicit明确的
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

    // 扩容
    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

    // huge 巨大
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE;
    }

    // 测试浅克隆
    private static void testArrayListClone() {
        ArrayList list1 = new ArrayList();
        list1.add(new Object());
        ArrayList list2 = (ArrayList) list1.clone();
        System.out.println(list1 == list2); // false，ArrayList对象是新的
        System.out.println(list1.get(0) == list2.get(0)); // true，内容引用是一样的
    }

    // 序列化使用，实现参见ArrayList源码
    private void readObject(java.io.ObjectInputStream s)
            throws java.io.IOException, ClassNotFoundException {
    }

    private void writeObject(java.io.ObjectOutputStream s)
            throws java.io.IOException {
    }

    /*
    序列化ArrayList
    其实就是如果对象中有readObject和writeObject，就会用对象的这两个方法进行序列化和反序列化
     */
    private static void testSerializeArrayList() {
        String objPath = "D:\\array.obj";
        ArrayList l = new ArrayList();
        l.add("aaa");
        l.add("bbb");
        // 序列化，写到硬盘
        try (ObjectOutputStream oos = new ObjectOutputStream(
                new FileOutputStream(objPath))) {
            oos.writeObject(l);
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        }
        System.out.println("写到硬盘：" + l);
        l.clear();
        l = null;

        try (ObjectInputStream ois = new ObjectInputStream(
                new FileInputStream(objPath))) {
            l = (ArrayList) ois.readObject();
        } catch (FileNotFoundException e) {
            e.printStackTrace();
        } catch (IOException e) {
            e.printStackTrace();
        } catch (ClassNotFoundException e) {
            e.printStackTrace();
        }

        System.out.println("读取硬盘：" + l);
    }

    // 用Iterator、ForEach遍历时，如果修改ArrayList，则抛异常 ConcurrentModificationException
    private static void testModCount() {
        ArrayList<Integer> list = new ArrayList<Integer>();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        Iterator<Integer> iterator = list.iterator();
        while (iterator.hasNext()) {
            Integer integer = iterator.next(); // modCount != expectedModCount ==> ConcurrentModificationException
            System.out.println(integer);
            if (integer == 2) {
//                list.remove(integer);   // ConcurrentModificationException
                iterator.remove(); // 可以
            }
        }
    }

    public static void main(String[] args) {
//        testSerializeArrayList();
//        testArrayListClone();
        testModCount();
    }


    // 内部方法
    private void rangeCheck(int index) {
        if (index >= size) throw new IndexOutOfBoundsException("...");
    }

    private void rangeCheckForAdd(int index) {
        if (index > size || index < 0) throw new IndexOutOfBoundsException("...");
    }
}
